package zw_101_200.zw_169_多数元素;


import java.util.HashMap;
import java.util.Map;

/**
 * 给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
 *
 * 你可以假设数组是非空的，并且给定的数组总是存在多数元素。
 *
 *  
 *
 * 示例 1：
 *
 * 输入：nums = [3,2,3]
 * 输出：3
 * 示例 2：
 *
 * 输入：nums = [2,2,1,1,1,2,2]
 * 输出：2
 *  
 *
 * 提示：
 * n == nums.length
 * 1 <= n <= 5 * 104
 * -109 <= nums[i] <= 109
 *  
 *
 * 进阶：尝试设计时间复杂度为 O(n)、空间复杂度为 O(1) 的算法解决此问题。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/majority-element
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */



class Solution {

    public static void main(String[] args) {
        int[] nums = {2,2,1,1,1,2,2};
        int element = majorityElement(nums);
        System.out.println(element);
    }

    /**
     * 哈希表
     * 复杂度分析：
     * 时间复杂度：O(n)，n为nums数组的长度。
     * 空间复杂度：O(n），哈希表需要的空间
     * @param nums
     * @return
     */
    public static int majorityElement(int[] nums) {
        Map<Integer,Integer> obj = new HashMap<>();
        for(int num : nums){
            obj.put(num, obj.getOrDefault(num, 0) + 1);
            if(obj.get(num) > nums.length / 2) return num;
        }
        return 0;
    }



    /**
     * 摩尔投票法
     * 候选人(cand_num)初始化为nums[0]，票数count初始化为1。
     * 当遇到与cand_num相同的数，则票数count = count + 1，否则票数count = count - 1。
     * 当票数count为0时，更换候选人，并将票数count重置为1。
     * 遍历完数组后，cand_num即为最终答案。
     *
     * 为何这行得通呢？
     * 投票法是遇到相同的则票数 + 1，遇到不同的则票数 - 1。
     * 且“多数元素”的个数> ⌊ n/2 ⌋，其余元素的个数总和<= ⌊ n/2 ⌋。
     * 因此“多数元素”的个数 - 其余元素的个数总和 的结果 肯定 >= 1。
     * 这就相当于每个“多数元素”和其他元素 两两相互抵消，抵消到最后肯定还剩余至少1个“多数元素”。
     * 无论数组是1 2 1 2 1，亦或是1 2 2 1 1，总能得到正确的候选人。
     * 时间复杂度：O(n)。Boyer-Moore 算法只对数组进行了一次遍历。
     *
     * 空间复杂度：O(1)。Boyer-Moore 算法只需要常数级别的额外空间。
     * @param nums
     * @return
     */
//    public static int majorityElement(int[] nums) {
//        int cand_num = nums[0], count = 1;
//        for (int i = 1; i < nums.length; ++i) {
//            if (cand_num == nums[i])
//                ++count;
//            else if (--count == 0) {
//                cand_num = nums[i];
//                count = 1;
//            }
//        }
//        return cand_num;
//    }


    /**
     * 排序+位运算
     * 既然数组中有出现次数> ⌊n/2⌋的元素，那排好序之后的数组中，相同元素总是相邻的。
     * 即存在长度> ⌊ n/2 ⌋的一长串 由相同元素构成的连续子数组。
     * 举个例子：
     * 无论是1 1 1 2 3，0 1 1 1 2还是-1 0 1 1 1，数组中间的元素总是“多数元素”，毕竟它长度> ⌊ n/2 ⌋。
     * @param nums
     * @return
     */
//    public static int majorityElement(int[] nums) {
//        Arrays.sort(nums);
//        return nums[nums.length >> 1];
//    }

}
